Greg Detre
@14:30 on Wednesday, October 02,
2002
prune
search space
forward searching � trying to realise that you
have a conflict higher up the tree rather than waiting till you get the bottom
arc consistency � assign values to a subset of
variables, already doing some forward checking (1-consistency), also check
constraints in the unassigned subset, all the way up to k-consistency (where
you�re checking everything)
heuristics
find the one with the largest domain size
find which one is most constrained
use databases � there must be some trade-off between space and time that
has been studied
least constraining value
heavy tails
use randomisation
complete
state formulation � specifies a valuable for every variable while you�re
searching
random walk
is complete � if all of space is reachable � so it dpeends on your local state
operator
ridge �
although the points are close in state space, they�re unreachable as neighbours
because of your local operator operator representation
the heuristic repair search solves the million queens in c.
50 steps � astonishing � that�s 106x106
provably
you will find the global optimum (with high probability???) with simulated
annealing if you move the temperature down slowly enough
it�s called �annealing� because it looks like an energy term
you can say
these are complete + optimal, but they don�t know when they�ve found the global
optimum � unlike systematic searches, because they maintain bounds
Tabu search
�???
Mitzenmacher � used it to find a new sequencing for an amino acid chain
helps to avoid cycles
Cooperative
search (Clearwater et al.)
originated from imagining multi-agent environment
exchange hints with each other to help solve the problem, and decide
when to use these hints
�???
GAs
think of crossovers as an exchange of hints
for crossover to work well, there has to be some modularity to your
representation so that breaking it up into chunks helps
GAs don�t usually do as well as other equivalent algorithms
key local
search ideas
communication (reachability)
diversification
intensification
largest
domain size vs most constrained???
is
stochastic beam search different from GAs at all???
y, it doesn�t derive from two parents
how many 8-queens solutions???
complete (vs optimal)???
in cooperative search, what�s a hint??? related to GA crossover